package com.github.yangyishe.p200;

import com.github.yangyishe.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 105. 从前序与中序遍历序列构造二叉树
 * https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/?envType=study-plan-v2&envId=top-interview-150
 * 官方优化的地方, 在于快速寻找中位索引
 *
 * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 *
 *
 *
 * 示例 1:
 *
 *
 * 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * 输出: [3,9,20,null,null,15,7]
 * 示例 2:
 *
 * 输入: preorder = [-1], inorder = [-1]
 * 输出: [-1]
 *
 *
 * 提示:
 *
 * 1 <= preorder.length <= 3000
 * inorder.length == preorder.length
 * -3000 <= preorder[i], inorder[i] <= 3000
 * preorder 和 inorder 均 无重复 元素
 * inorder 均出现在 preorder
 * preorder 保证 为二叉树的前序遍历序列
 * inorder 保证 为二叉树的中序遍历序列
 */
public class Problem105 {
    public static void main(String[] args) {
        int[] preorder=new int[]{3,9,20,15,7};
        int[] inorder=new int[]{9,3,15,20,7};

        Problem105 problem105 = new Problem105();
        TreeNode treeNode = problem105.buildTree(preorder, inorder);
        treeNode.preOrder();

    }

    private Map<Integer,Integer> inVal2IndexMap=new HashMap<>();

    /**
     * 前置:
     * 前序遍历中, 获取第一个数字, 即为树顶的值.
     * 在中序遍历中找到该值索引, 则该值左侧必在树顶的左子树上, 右侧必在右侧的左子树上.
     * 据此获得左右两子树的size, 进而可在前序遍历的集合中切割开, 从而分别获得左右子树对应的前序遍历和中序遍历.
     * 以此类推, 可继续推演, 直到子树的size=1, 即构建出一个节点
     *
     *
     * 思路:
     * 可考虑使用分治算法.
     *
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0){
            return null;
        }
        for(int i=0;i<inorder.length;i++){
            inVal2IndexMap.put(inorder[i],i);
        }

        return buildTreeNode(preorder,inorder,0,preorder.length-1,0,inorder.length-1);

    }



    public TreeNode buildTreeNode(int[] preorder,int[] inorder,int preStart,int preEnd,int inStart,int inEnd){
        if (preStart==preEnd) {
            return new TreeNode(preorder[preStart]);
        }
        int topInfixIndex=inVal2IndexMap.get(preorder[preStart]);

        TreeNode topNode = new TreeNode(preorder[preStart]);
        // leftSize+rightSize+1=totalSize
        int leftSize=topInfixIndex-inStart;
        if(leftSize>0){
            topNode.left=buildTreeNode(preorder,inorder,preStart+1,preStart+leftSize,inStart,topInfixIndex-1);
        }

        int rightSize=inEnd-topInfixIndex;
        if(rightSize>0){
            topNode.right=buildTreeNode(preorder,inorder,preStart+leftSize+1,preEnd,topInfixIndex+1,inEnd);
        }

        return topNode;
    }
}
